{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Reorder List"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #recursion #linked-list #two-pointers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #递归 #链表 #双指针"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: reorderList"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #重排链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个单链表 <code>L</code><em> </em>的头节点 <code>head</code> ，单链表 <code>L</code> 表示为：</p>\n",
    "\n",
    "<pre>\n",
    "L<sub>0</sub> → L<sub>1</sub> → … → L<sub>n - 1</sub> → L<sub>n</sub>\n",
    "</pre>\n",
    "\n",
    "<p>请将其重新排列后变为：</p>\n",
    "\n",
    "<pre>\n",
    "L<sub>0</sub> → L<sub>n</sub> → L<sub>1</sub> → L<sub>n - 1</sub> → L<sub>2</sub> → L<sub>n - 2</sub> → …</pre>\n",
    "\n",
    "<p>不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://pic.leetcode-cn.com/1626420311-PkUiGI-image.png\" style=\"width: 240px; \" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1,2,3,4]\n",
    "<strong>输出：</strong>[1,4,2,3]</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://pic.leetcode-cn.com/1626420320-YUiulT-image.png\" style=\"width: 320px; \" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1,2,3,4,5]\n",
    "<strong>输出：</strong>[1,5,2,4,3]</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>链表的长度范围为 <code>[1, 5 * 10<sup>4</sup>]</code></li>\n",
    "\t<li><code>1 &lt;= node.val &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [reorder-list](https://leetcode.cn/problems/reorder-list/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [reorder-list](https://leetcode.cn/problems/reorder-list/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4]', '[1,2,3,4,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def reorderList(self, head):\n",
    "    \"\"\"\n",
    "    :type head: ListNode\n",
    "    :rtype: void Do not return anything, modify head in-place instead.\n",
    "    \"\"\"\n",
    "    if head == None:\n",
    "      return head\n",
    "\n",
    "    p, listLen = head, 0\n",
    "    while p != None:\n",
    "      p, listLen = p.next, listLen + 1\n",
    "    leftLen = listLen // 2 + listLen % 2\n",
    "\n",
    "    q = head\n",
    "    for i in range( leftLen ):\n",
    "      p, q = q, q.next\n",
    "    p.next = None\n",
    "\n",
    "    stack = list()\n",
    "    while q != None:\n",
    "      p, q = q, q.next\n",
    "      p.next = None\n",
    "      stack.append( p )\n",
    "\n",
    "    p = head\n",
    "    while len( stack ) > 0:\n",
    "      q = stack.pop()\n",
    "      q.next = p.next\n",
    "      p.next = q\n",
    "      p = q.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reorderList(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: void Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        if head==None or head.next==None or head.next.next==None:\n",
    "            return\n",
    "        \n",
    "        slow = fast = head\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        head1 = head\n",
    "        head2 = slow.next\n",
    "        slow.next = None\n",
    "    \n",
    "        # reverse head2 list\n",
    "        print(head1)\n",
    "        print(head2)\n",
    "        pre,cur,nxt = None,head2,None\n",
    "        while cur:\n",
    "            nxt = cur.next\n",
    "            cur.next= pre # 让当前节点指向 pre\n",
    "            \n",
    "            # 更新 pre \n",
    "            pre = cur\n",
    "            cur = nxt\n",
    "        head2 = pre\n",
    "        print(head2)\n",
    "        \n",
    "        p1,p2 = head1,head2\n",
    "        while p2:\n",
    "            tmp1 = p1.next\n",
    "            tmp2 = p2.next\n",
    "            p1.next = p2\n",
    "            p2.next = tmp1\n",
    "            p1 = tmp1\n",
    "            p2 = tmp2\n",
    "            \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "            \n",
    "            \n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reorderList(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: void Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        if not head or not head.next:\n",
    "            return \n",
    "        \n",
    "        fast,slow,prev=head,head,None\n",
    "        \n",
    "        while fast and fast.next:\n",
    "            prev=slow\n",
    "            fast=fast.next.next\n",
    "            slow=slow.next\n",
    "\n",
    "        prev.next=None\n",
    "        slow=self.reverse(slow)\n",
    "        cur,pre=head,None\n",
    "        \n",
    "        while cur:\n",
    "            pre=slow\n",
    "            temp1=cur.next\n",
    "            temp2=slow.next\n",
    "            cur.next=slow\n",
    "            slow.next=temp1\n",
    "            cur=temp1\n",
    "            slow=temp2\n",
    "        pre.next=slow\n",
    "        return \n",
    "        \n",
    "            \n",
    "    def reverse(self,head):\n",
    "        pre=None\n",
    "        \n",
    "        while head:\n",
    "            temp=head.next\n",
    "            head.next=pre\n",
    "            pre=head\n",
    "            head=temp\n",
    "            \n",
    "        return pre\n",
    "        \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reorderList(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: void Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        p = head\n",
    "        \n",
    "        if(head==None):\n",
    "            return \n",
    "        arr = []\n",
    "        while(p!=None):\n",
    "            arr.append(p)\n",
    "            p = p.next\n",
    "        if(len(arr)==1):\n",
    "            return \n",
    "        brr = arr[(len(arr)+1)//2:]+[]\n",
    "        arr = arr[:(len(arr)+1)//2]\n",
    "        \n",
    "        pre = None\n",
    "        for x,y in zip(arr,brr[::-1]):\n",
    "            if pre==None:\n",
    "                x.next = y\n",
    "                pre = y\n",
    "            else:\n",
    "                pre.next = x\n",
    "                x.next = y\n",
    "                pre = y\n",
    "                pass\n",
    "        if(len(arr)!=len(brr)):\n",
    "            pre.next = arr[-1]\n",
    "            arr[-1].next = None\n",
    "        else:\n",
    "            pre.next = None\n",
    "        return \n",
    "        \n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reorderList(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: void Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        if head == None or head.next == None or head.next.next == None:\n",
    "            return\n",
    "        cur = head\n",
    "        l = []\n",
    "        while cur != None:\n",
    "            l.append(cur.val)\n",
    "            cur = cur.next\n",
    "        templ = l.copy()\n",
    "        templ.reverse()\n",
    "        res = []\n",
    "        for i in range(len(l)//2):\n",
    "            res.append(l[i])\n",
    "            res.append(templ[i])\n",
    "        if len(l) % 2 != 0:\n",
    "            res.append(l[len(l)//2])\n",
    "        cur = head\n",
    "        i = 0\n",
    "        while cur != None:\n",
    "            cur.val = res[i]\n",
    "            i += 1\n",
    "            cur = cur.next\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        if head is None or head.next is None:\n",
    "            return head\n",
    "\n",
    "        i = head\n",
    "        j = head.next\n",
    "\n",
    "        # 找中点\n",
    "        while j is not None and j.next is not None:\n",
    "            j = j.next.next\n",
    "            i = i.next\n",
    "\n",
    "        mid = i\n",
    "        right = i.next\n",
    "        i.next = None # 断开链表\n",
    "\n",
    "        # 右边链表反转\n",
    "        pre = None\n",
    "        while right is not None:\n",
    "            right_next = right.next\n",
    "            right.next = pre\n",
    "            pre = right\n",
    "            right = right_next\n",
    "\n",
    "        # 获取反转后的表头\n",
    "        right = pre\n",
    "        left = head\n",
    "\n",
    "        # 穿插操作\n",
    "        while left is not None and right is not None:\n",
    "            left_next = left.next\n",
    "            right_next = right.next\n",
    "\n",
    "            # 插入节点\n",
    "            left.next = right\n",
    "            right.next = left_next\n",
    "\n",
    "            left = left_next\n",
    "            right = right_next\n",
    "            \n",
    "        \n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        if not head:\n",
    "            return None\n",
    "\n",
    "        allNodes = []\n",
    "        node = head\n",
    "        while node:\n",
    "            allNodes.insert(0, node)\n",
    "            node = node.next\n",
    "\n",
    "        node = head\n",
    "        count = len(allNodes)//2\n",
    "        l = count\n",
    "        while count>0:\n",
    "            nextNextNode = node.next\n",
    "            nextNode = allNodes[l-count]\n",
    "            node.next = nextNode\n",
    "            nextNode.next = nextNextNode\n",
    "            node = nextNextNode\n",
    "            # allNodes.pop(0)\n",
    "            count -= 1\n",
    "        node.next = None\n",
    "\n",
    "        return head\n",
    "        \n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        if not head:\n",
    "            return None\n",
    "        Merged_head = merge = ListNode(0)\n",
    "\n",
    "        slow = fast = head\n",
    "        while fast.next:\n",
    "            pNext = fast.next\n",
    "            if pNext.next:\n",
    "                slow = slow.next\n",
    "                fast = pNext.next\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        temp = slow.next\n",
    "        back = self.reverseList(temp)\n",
    "        slow.next = None\n",
    "\n",
    "        i = 1\n",
    "        while head and back:\n",
    "            if i & 1 == 1:\n",
    "                merge.next = head\n",
    "                merge = merge.next\n",
    "                head = head.next\n",
    "            else:\n",
    "                merge.next = back\n",
    "                merge = merge.next\n",
    "                back = back.next\n",
    "            i += 1\n",
    "\n",
    "        if head:\n",
    "            merge.next = head\n",
    "        if back:\n",
    "            merge.next = back\n",
    "\n",
    "        return Merged_head.next\n",
    "\n",
    "    def reverseList(self, head):\n",
    "        if not head:\n",
    "            return None\n",
    "        preNode = None\n",
    "        pNode = head\n",
    "        while pNode:\n",
    "            pNext = pNode.next\n",
    "            pNode.next = preNode\n",
    "            preNode = pNode\n",
    "            pNode = pNext\n",
    "\n",
    "        return preNode"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "\"\"\"\n",
    "我觉得可以找到linked list的中心，然后把后半部分给revert了\n",
    "接下来重新merge\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        if not head:\n",
    "            return head\n",
    "        # Find middle of the list\n",
    "        slow = head\n",
    "        fast = head\n",
    "        while fast.next and fast.next.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        second_half_head = slow.next\n",
    "        slow.next = None\n",
    "        # rever second half\n",
    "        prev = None\n",
    "        while second_half_head:\n",
    "            nex = second_half_head.next\n",
    "            second_half_head.next = prev\n",
    "            prev = second_half_head\n",
    "            second_half_head = nex\n",
    "        second_half_head = prev\n",
    "        # merge\n",
    "        dummy = ListNode(-1)\n",
    "        curr = dummy\n",
    "        while head and second_half_head:\n",
    "            curr.next = head\n",
    "            head = head.next\n",
    "            curr.next.next = second_half_head\n",
    "            second_half_head = second_half_head.next\n",
    "            curr = curr.next.next\n",
    "        if head:\n",
    "            curr.next = head\n",
    "            head.next = None\n",
    "        return dummy.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def reorderList(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: None Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        if not head: return None\n",
    "        p = head\n",
    "        stack = []\n",
    "        # 把所有节点压入栈中\n",
    "        while p:\n",
    "            stack.append(p)\n",
    "            p = p.next\n",
    "        # 长度\n",
    "        n = len(stack)\n",
    "        # 找到中点前一个位置 \n",
    "        count = (n - 1) // 2\n",
    "        p = head\n",
    "        while count:\n",
    "            # 弹出栈顶\n",
    "            tmp = stack.pop()\n",
    "            # 与链头拼接\n",
    "            tmp.next = p.next\n",
    "            p.next  = tmp\n",
    "            # 移动一个位置\n",
    "            p = tmp.next\n",
    "            count -= 1\n",
    "        stack.pop().next = None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        else:\n",
    "            slow = fast = head\n",
    "            while fast and fast.next:\n",
    "                fast = fast.next.next\n",
    "                slow = slow.next\n",
    "            mid = slow\n",
    "            rightHead = mid.next\n",
    "            mid.next = None\n",
    "\n",
    "            prev, cur = None, rightHead\n",
    "            while cur:\n",
    "                tmp = cur.next\n",
    "                cur.next = prev\n",
    "                prev = cur\n",
    "                cur = tmp\n",
    "            rightHead = prev\n",
    "\n",
    "            left, right = head, rightHead\n",
    "            while left and right:\n",
    "                tmp = left.next\n",
    "                left.next = right\n",
    "                left = tmp\n",
    "                tmp = right.next\n",
    "                right.next = left\n",
    "                right = tmp\n",
    "            \n",
    "            return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "\n",
    "class Solution:\n",
    "    def reorderList(self, head: Optional[ListNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        # 方法1： 数组存储链表，并采用前后指针生成目标链表\n",
    "        if not head:\n",
    "            return\n",
    "\n",
    "        node = head\n",
    "        tmp = []  # 保存链表节点\n",
    "        while node:\n",
    "            tmp.append(node)\n",
    "            node = node.next\n",
    "\n",
    "        i, j = 0, len(tmp)-1\n",
    "        while i < j:\n",
    "            tmp[i].next = tmp[j]\n",
    "            i += 1\n",
    "\n",
    "            if i == j:  # 若为奇数，此时判断左右指针是否相等，若相等，表示中间节点已经添加，终止遍历\n",
    "                break\n",
    "\n",
    "            tmp[j].next = tmp[i]\n",
    "            j -= 1\n",
    "        tmp[i].next = None  # 链表结束\n",
    "\n",
    "        # def reverse_list(head_):\n",
    "        #     # 反转链表，返回反转后的链表头\n",
    "        #     if not head_ or not head_.next:\n",
    "        #         return head\n",
    "        #\n",
    "        #     pre = None\n",
    "        #     while head_:\n",
    "        #         tmp = head_.next  # 保存当前节点的下一位\n",
    "        #         head.next = pre\n",
    "        #         # pre 和 head 往前移\n",
    "        #         pre = head_\n",
    "        #         head_ = tmp\n",
    "        #     return pre\n",
    "        #\n",
    "        # # 方法1：快慢指针，找到链表中间位置，从中间位置反转后续链表\n",
    "        # if not head or not head.next:\n",
    "        #     return\n",
    "        # # 找到链表中间位置\n",
    "        # slow, fast = head, head.next\n",
    "        # while fast and fast.next:\n",
    "        #     slow, fast = slow.next, fast.next.next\n",
    "        # new_head = slow.next\n",
    "        # slow.next = None  # 否则会超时\n",
    "        # # 反转后续链表\n",
    "        # new_head = reverse_list(new_head)\n",
    "        #\n",
    "        # while new_head:\n",
    "        #     post = new_head.next\n",
    "        #     new_head.next = head.next\n",
    "        #     head.next = new_head\n",
    "        #     head = new_head.next\n",
    "        #     new_head = post\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: Optional[ListNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        pre=ListNode()\n",
    "        pre.next=head\n",
    "        low,fast=pre,pre\n",
    "        while fast and fast.next:\n",
    "            low=low.next\n",
    "            fast=fast.next.next\n",
    "        fast=low.next\n",
    "        low.next=None\n",
    "        last=None\n",
    "        while fast:\n",
    "            tmp=fast.next\n",
    "            fast.next=last\n",
    "            last=fast\n",
    "            fast=tmp\n",
    "        \n",
    "        fast=last\n",
    "        low=head\n",
    "        while low and fast:\n",
    "            tmp=fast.next\n",
    "            fast.next=low.next\n",
    "            low.next=fast\n",
    "            low=fast.next\n",
    "            fast=tmp\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        if not head:\n",
    "            return\n",
    "        \n",
    "        vec = list()\n",
    "        node = head\n",
    "        while node:\n",
    "            vec.append(node)\n",
    "            node = node.next\n",
    "        \n",
    "        i, j = 0, len(vec) - 1\n",
    "        while i < j:\n",
    "            vec[i].next = vec[j]\n",
    "            i += 1\n",
    "            if i == j:\n",
    "                break\n",
    "            vec[j].next = vec[i]\n",
    "            j -= 1\n",
    "        \n",
    "        vec[i].next = None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        if not head:\n",
    "            return\n",
    "        \n",
    "        vec = list()\n",
    "        node = head\n",
    "        while node:\n",
    "            vec.append(node)\n",
    "            node = node.next\n",
    "        \n",
    "        i, j = 0, len(vec) - 1\n",
    "        while i < j:\n",
    "            vec[i].next = vec[j]\n",
    "            i += 1\n",
    "            if i == j:\n",
    "                break\n",
    "            vec[j].next = vec[i]\n",
    "            j -= 1\n",
    "        \n",
    "        vec[i].next = None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: Optional[ListNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        slow,fast = head,head\n",
    "        while fast.next and fast.next.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        cur = slow.next\n",
    "        slow.next = None\n",
    "        pre = None\n",
    "        while cur:\n",
    "            nxt = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = nxt\n",
    "        \n",
    "        cur = head\n",
    "        while pre:\n",
    "            t = pre.next\n",
    "            pre.next = cur.next\n",
    "            cur.next = pre\n",
    "            cur = pre.next\n",
    "            pre = t\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: Optional[ListNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        middle_node = self.find_middle_node(head)\n",
    "        # print(middle_node.val)\n",
    "        reversed_node = self.reverse_linklist(middle_node)\n",
    "        head1 = head\n",
    "        head2 = reversed_node\n",
    "        # while head1 and head2:\n",
    "        #     print(head1.val, head2.val)\n",
    "        #     head1 = head1.next\n",
    "        #     head2 = head2.next\n",
    "        # while head1:\n",
    "        #     print(head1.val)\n",
    "        #     head1 = head1.next\n",
    "        # while head2:\n",
    "        #     print(head2.val)\n",
    "        #     head2 = head2.next\n",
    "        # # print(head1.val, head2.val)\n",
    "        while head2.next:\n",
    "            # print(head1.val, head2.val)\n",
    "            nxt1 = head1.next\n",
    "            nxt2 = head2.next\n",
    "            head1.next = head2\n",
    "            head2.next = nxt1\n",
    "            print(head1.val, head2.val)\n",
    "            head1 = nxt1\n",
    "            head2 = nxt2\n",
    "\n",
    "\n",
    "    def find_middle_node(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        slow = head\n",
    "        fast = head\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        return slow\n",
    " \n",
    "    def reverse_linklist(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        pre = None\n",
    "        cur = head\n",
    "        while cur:\n",
    "            nxt = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = nxt\n",
    "        return pre\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: Optional[ListNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        i = 0\n",
    "        cur = head\n",
    "        address = {}\n",
    "        while cur is not None:\n",
    "            address[i] = cur\n",
    "            i += 1\n",
    "            cur = cur.next\n",
    "        length = len(address)\n",
    "        i, j = 0, length-1\n",
    "        while i<j-1:\n",
    "            print(i,j)\n",
    "            address[j-1].next = address[j].next\n",
    "            address[i].next = address[j]\n",
    "            address[j].next = address[i+1]\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        return\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: Optional[ListNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        lookUp = dict()\n",
    "        i = 0\n",
    "        while head:\n",
    "            lookUp[i] = head\n",
    "            head = head.next\n",
    "            i += 1\n",
    "        left = 0\n",
    "        right = i - 1\n",
    "        dummyHead = ListNode()\n",
    "        node = dummyHead\n",
    "        direc = 0\n",
    "        while left <= right:\n",
    "            if direc == 0:\n",
    "                node.next = lookUp[left]\n",
    "                node = node.next\n",
    "                left += 1\n",
    "                direc = 1 - direc\n",
    "            else:\n",
    "                node.next = lookUp[right]\n",
    "                node = node.next\n",
    "                right -= 1\n",
    "                direc = 1 - direc\n",
    "        node.next = None\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: Optional[ListNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        lst=[]\n",
    "        p=head\n",
    "        while p:\n",
    "            lst.append(p.val)\n",
    "            p=p.next\n",
    "        res=lst[1:][::-1]\n",
    "        q=head\n",
    "        for i in res:\n",
    "            newNode=ListNode(i)\n",
    "            newNode.next=q.next\n",
    "            q.next=newNode\n",
    "            q=q.next.next\n",
    "        r=head\n",
    "        for i in range(len(lst)-1):\n",
    "            r=r.next\n",
    "        r.next=None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: Optional[ListNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        if not head:\n",
    "            return\n",
    "        stack = []\n",
    "        headnode = head\n",
    "        count = 0\n",
    "        while headnode:\n",
    "            stack.append(headnode.val)\n",
    "            headnode = headnode.next\n",
    "            count = count + 1\n",
    "        k = count//2 \n",
    "        dummpy = ListNode()\n",
    "        cur = dummpy\n",
    "        for i in range(k):\n",
    "            cur.next = head\n",
    "            head = head.next\n",
    "            cur = cur.next\n",
    "            a = ListNode(stack[-1])\n",
    "            cur.next = a\n",
    "            stack.pop()\n",
    "            cur = cur.next\n",
    "        if count%2 !=0:\n",
    "            cur.next = head\n",
    "            head = head.next\n",
    "            cur = cur.next\n",
    "            cur.next = None\n",
    "        return dummpy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: Optional[ListNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        d = {}\n",
    "        cur = head\n",
    "        n = 0\n",
    "        while cur:\n",
    "            d[n]=cur\n",
    "            cur = cur.next\n",
    "            n = n+1\n",
    "        n = n-1\n",
    "        for i in range((n)//2):\n",
    "            start = i\n",
    "            end = n-i\n",
    "            end_1 = n-i-1\n",
    "            start_1 = i+1\n",
    "            d[start].next=d[end]\n",
    "            d[end].next = d[start_1]\n",
    "            d[end_1].next=None\n",
    "        return head\n",
    "        # if head is None:\n",
    "        #     return None\n",
    "        \n",
    "        # if head.next is None or head.next.next is None:\n",
    "        #     return head\n",
    "        # end = head\n",
    "        # pre = head\n",
    "        # while pre.next.next:\n",
    "        #     pre = pre.next  \n",
    "        # while end.next:\n",
    "        #     end = end.next\n",
    "        # temp = head.next\n",
    "        # head.next = end\n",
    "        # pre.next=None\n",
    "        # end.next=self.reorderList(temp)\n",
    "        # return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: Optional[ListNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        lookUp = dict()\n",
    "        count = 0\n",
    "        while head:\n",
    "            lookUp[count] = head\n",
    "            count += 1\n",
    "            head = head.next\n",
    "        count -= 1\n",
    "        left = 0\n",
    "        right = count\n",
    "        direc = 0\n",
    "        dummyHead = ListNode()\n",
    "        node = dummyHead\n",
    "        while left <= right:\n",
    "            if direc == 0:\n",
    "                node.next = lookUp[left]\n",
    "                left += 1\n",
    "            else:\n",
    "                node.next = lookUp[right]\n",
    "                right -= 1\n",
    "            direc = 1 - direc\n",
    "            node = node.next\n",
    "        node.next = None\n",
    "        return dummyHead.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: Optional[ListNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        # 先逆序\n",
    "        if not head.next:\n",
    "            return head\n",
    "        def reverseListNode(head):\n",
    "            if head==None:\n",
    "                return None\n",
    "            rear=ListNode(head.val)\n",
    "            while head!=None:\n",
    "                b=ListNode(head.val)\n",
    "                b.next=rear.next\n",
    "                rear.next=b\n",
    "                head=head.next\n",
    "            return rear.next\n",
    "        q=head\n",
    "        reverseList=reverseListNode(q)\n",
    "        p=head\n",
    "        rear=reverseList\n",
    "        res_=ListNode(-1)\n",
    "        res=res_\n",
    "        l_new=0\n",
    "        l_temp=0\n",
    "        p_=head\n",
    "        while p_:\n",
    "            l_temp+=1\n",
    "            # print(p_.val)\n",
    "            p_=p_.next\n",
    "        # while rear:\n",
    "        #     print(rear.val)\n",
    "        #     rear=rear.next\n",
    "\n",
    "        while p and rear and l_new<l_temp:\n",
    "            # print(l_new,l_temp)\n",
    "            if l_new<l_temp:\n",
    "                temp=p\n",
    "                p=p.next\n",
    "                res.next=temp\n",
    "                res=res.next\n",
    "                l_new+=1\n",
    "            if l_new<l_temp:\n",
    "                temp=rear\n",
    "                rear=rear.next\n",
    "                res.next=temp\n",
    "                res=res.next\n",
    "                l_new+=1\n",
    "        res.next=None\n",
    "        return res_.next\n",
    "        \n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: Optional[ListNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        norm = renorm = head\n",
    "        renorm_ = None\n",
    "        L = 0\n",
    "        while renorm:\n",
    "            renorm_ = ListNode(val=renorm.val, next=renorm_)\n",
    "            renorm = renorm.next\n",
    "            L += 1\n",
    "        head0 = head1 = ListNode()\n",
    "        for i in range(L//2):\n",
    "            head1.val = norm.val\n",
    "            norm = norm.next\n",
    "            head1.next = ListNode()\n",
    "            head1 = head1.next\n",
    "\n",
    "            head1.val=renorm_.val\n",
    "            if i < L//2-1 or L%2:\n",
    "                head1.next=ListNode()\n",
    "            renorm_ = renorm_.next\n",
    "            head1 = head1.next\n",
    "        if L%2:\n",
    "            head1.val = norm.val\n",
    "        \n",
    "        head.val = head0.val\n",
    "        head.next = head0.next\n",
    "        \n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: Optional[ListNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        newHead = ListNode(-1)\n",
    "        prev = None\n",
    "        curr = head\n",
    "        n = 0\n",
    "\n",
    "        while curr:\n",
    "            node = ListNode(curr.val)\n",
    "            node.next = prev\n",
    "            prev = node\n",
    "            curr = curr.next\n",
    "            n += 1\n",
    "\n",
    "        head2 = prev\n",
    "        dumyHead = ListNode(-1)\n",
    "        p0 = head\n",
    "        p1 = head2\n",
    "        p2 = dumyHead\n",
    "        for i in range(n//2):\n",
    "            tmp1 = p0.next\n",
    "            tmp2 = p1.next\n",
    "            p2.next = p0\n",
    "            p2.next.next = p1\n",
    "            \n",
    "            p0 = tmp1\n",
    "            p1 = tmp2\n",
    "            p2 = p2.next.next\n",
    "\n",
    "        if n % 2 != 0:\n",
    "            p2.next = ListNode(p0.val)\n",
    "            p2.next.next = None\n",
    "        else:\n",
    "            p2.next = None\n",
    "            \n",
    "        return dumyHead.next            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        # 超时\n",
    "        # if not head or not head.next or not head.next.next:\n",
    "        #     return\n",
    "        # nxt = head.next\n",
    "        # last = head\n",
    "        # while last.next.next:\n",
    "        #     last = last.next\n",
    "        # head.next = last.next\n",
    "        # last.next.next = nxt\n",
    "        # last.next = None\n",
    "        # self.reorderList(nxt)\n",
    "        if not head or not head.next or not head.next.next:\n",
    "            return\n",
    "        slow, fast = head, head.next\n",
    "        while fast and fast.next:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "        listnode2 = slow.next\n",
    "        slow.next = None\n",
    "        listnode2 = self.revList(listnode2)\n",
    "        i = head\n",
    "        j = listnode2\n",
    "        while j:\n",
    "            tmp = j.next\n",
    "            j.next = i.next\n",
    "            i.next = j\n",
    "            i = i.next.next\n",
    "            j = tmp\n",
    "\n",
    "    def revList(self, head):\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        tmp = self.revList(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return tmp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        if not head:\n",
    "            return None\n",
    "        slow = head\n",
    "        fast = head.next\n",
    "        while fast and fast.next:\n",
    "            fast=fast.next.next\n",
    "            slow = slow.next\n",
    "        \n",
    "        right = self.reverse(slow.next) #只要翻转右边就OK\n",
    "        slow.next = None\n",
    "        left = head\n",
    "\n",
    "        \n",
    "        dummy = ListNode(0)\n",
    "        p = dummy\n",
    "        while p:\n",
    "            next_left = left.next if left else None\n",
    "            next_right = right.next if right else None\n",
    "            p.next = left\n",
    "            p = left\n",
    "            if not p:\n",
    "                break\n",
    "            p.next = right\n",
    "            p = right\n",
    "            left = next_left\n",
    "            right = next_right\n",
    "\n",
    "        return\n",
    "\n",
    "        \n",
    "    \n",
    "    def reverse(self, head):\n",
    "        if not head or head.next==None:\n",
    "            return head\n",
    "        \n",
    "        newHead = self.reverse(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return newHead"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverse_stack(self, head):\n",
    "        new_head = ListNode(head.val)\n",
    "        head = head.next\n",
    "        i=1\n",
    "        while head:\n",
    "            tmp = ListNode(head.val)\n",
    "            tmp.next = new_head\n",
    "            new_head = tmp\n",
    "            head = head.next\n",
    "            i+=1\n",
    "        return new_head, i\n",
    "    def reorderList(self, head: Optional[ListNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        if head ==None or head.next==None:\n",
    "            return head\n",
    "        ori_head = head\n",
    "        reverse_head, length = self.reverse_stack(head)\n",
    "\n",
    "        new_head = ListNode(head.val)\n",
    "        tmp_head = new_head\n",
    "        head = head.next\n",
    "        length -= 1\n",
    "        while True:\n",
    "            \n",
    "            tmp = ListNode(reverse_head.val)\n",
    "            reverse_head = reverse_head.next\n",
    "            tmp_head.next = tmp\n",
    "            tmp_head = tmp\n",
    "            length -= 1\n",
    "            if length == 0:\n",
    "                ori_head.next = new_head.next\n",
    "                return ori_head\n",
    "            \n",
    "            tmp = ListNode(head.val)\n",
    "            head = head.next\n",
    "            tmp_head.next = tmp\n",
    "            tmp_head = tmp\n",
    "            length -= 1\n",
    "            if length == 0:\n",
    "                ori_head.next = new_head.next\n",
    "                return ori_head\n",
    "\n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        if head == None:\n",
    "            return None\n",
    "        if head.next == None:\n",
    "            return head\n",
    "        list1, list2 = self.split(head)\n",
    "        self.print(list1)\n",
    "        self.print(list2)\n",
    "        list2 = self.reverse(list2)\n",
    "        head = self.combine(list1, list2)\n",
    "\n",
    "    def print(self, head):\n",
    "        while head:\n",
    "            print(head.val)\n",
    "            head = head.next\n",
    "        print()\n",
    "\n",
    "    # def split(self, head):\n",
    "    #     list1, list2 = ListNode(0), ListNode(0)\n",
    "    #     cur1, cur2 = list1, list2\n",
    "    #     cur = head\n",
    "    #     while cur and cur.next:\n",
    "    #         temp1, temp2 = cur, cur.next\n",
    "    #         cur = cur.next.next\n",
    "    #         cur1.next, cur2.next = temp1, temp2\n",
    "    #         cur1, cur2 = cur1.next, cur2.next\n",
    "    #     if cur != None:\n",
    "    #         cur1.next = cur\n",
    "    #         cur1 = cur1.next\n",
    "    #     cur1.next = None\n",
    "    #     cur2.next = None\n",
    "    #     return list1.next, list2.next\n",
    "\n",
    "    def split(self, head):\n",
    "        slow, fast = head, head\n",
    "        pre = None\n",
    "        while fast and fast.next:\n",
    "            pre = slow\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        pre.next = None\n",
    "        return head, slow\n",
    "    \n",
    "    def reverse(self, head):\n",
    "        if head == None:\n",
    "            return None\n",
    "        if head.next == None:\n",
    "            return head\n",
    "        remain = self.reverse(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return remain\n",
    "    \n",
    "    def combine(self, list1, list2):\n",
    "        head = ListNode(0)\n",
    "        cur = head\n",
    "        while list1 and list2:\n",
    "            temp1, temp2 = list1, list2\n",
    "            list1, list2 = list1.next, list2.next\n",
    "            cur.next = temp1\n",
    "            cur = cur.next\n",
    "            cur.next = temp2\n",
    "            cur = cur.next\n",
    "        if list2 != None:\n",
    "            cur.next = list2\n",
    "            cur = cur.next\n",
    "            cur.next = None\n",
    "        return head\n",
    "\n",
    "        \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        if head is None or head.next is None or head.next.next is None:\n",
    "            return\n",
    "        stack = []\n",
    "        start = head\n",
    "        while start is not None:\n",
    "            stack.append(start)\n",
    "            start = start.next\n",
    "        self.reorderListHelper(head, stack)\n",
    "        return\n",
    "\n",
    "    def reorderListHelper(self, head, nodes):\n",
    "        if head.next is None:\n",
    "            return\n",
    "        tmp = head.next\n",
    "        new_next = nodes.pop()\n",
    "        if tmp == new_next:\n",
    "            return\n",
    "        else:\n",
    "            new_next.next = tmp\n",
    "            head.next = new_next\n",
    "            nodes[-1].next = None\n",
    "            self.reorderListHelper(tmp, nodes)\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        self.list_len = 0\n",
    "        tmp_head = head\n",
    "        while tmp_head != None:\n",
    "            self.list_len += 1\n",
    "            tmp_head = tmp_head.next\n",
    "        self.finish_index = (self.list_len - 1) // 2\n",
    "        self.curr_id = 0\n",
    "        head = head\n",
    "        self.head1 = head\n",
    "        for i in range(self.finish_index + 1):\n",
    "            self.head1 = self.head1.next\n",
    "        self.trace_back(head)\n",
    "\n",
    "\n",
    "    def trace_back(self, new_head):\n",
    "        head = new_head\n",
    "        if head.next == self.head1:\n",
    "            if self.list_len % 2 == 0:\n",
    "                self.head1 = self.head1.next\n",
    "                new_head.next.next = None\n",
    "            else:\n",
    "                new_head.next = None\n",
    "        else:\n",
    "            self.trace_back(head.next)\n",
    "            new_head1 = self.head1.next\n",
    "            self.head1.next = head.next\n",
    "            head.next = self.head1\n",
    "            self.head1 = new_head1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        if not head.next or not head.next.next:\n",
    "            return\n",
    "        middle = self.middleNode(head)\n",
    "        right = middle.next\n",
    "        middle.next = None\n",
    "        right = self.reverse(right)\n",
    "        left = head\n",
    "        while right:\n",
    "            tempr = right.next\n",
    "            templ = left.next\n",
    "            left.next = right\n",
    "            right.next = templ\n",
    "            left = templ\n",
    "            right = tempr\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "    def middleNode(self,head):\n",
    "        l = f = head\n",
    "        while f.next and f.next.next:\n",
    "            l = l.next\n",
    "            f = f.next.next\n",
    "        return l\n",
    "    def reverse(self,head):\n",
    "        if not head.next:\n",
    "            return head\n",
    "        if head.next:\n",
    "            r = self.reverse(head.next)\n",
    "            head.next.next = head\n",
    "            head.next = None\n",
    "            return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        if head or head.next:\n",
    "            fast, slow = head, head\n",
    "            while fast.next and fast.next.next:\n",
    "                fast = fast.next.next\n",
    "                slow = slow.next\n",
    "            # middle point of the list\n",
    "            pnt1 = slow\n",
    "            # reverse the right half part of list\n",
    "            pnt1 = self.reverseList(pnt1)\n",
    "            self.mergeList(head, pnt1)\n",
    "    # reverse the list\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        # 使用递归\n",
    "        # 这个列表长度小于等于1：\n",
    "        if head == None or head.next == None:\n",
    "            return head\n",
    "        # 列表长度大于1\n",
    "        new_head = self.reverseList(head.next)\n",
    "        # 从head.next开始，head.next的下一个为head,并且new_head到最后一个\n",
    "        head.next.next = head\n",
    "        # head.next为None, head变成tail\n",
    "        head.next = None\n",
    "        return new_head\n",
    "    # merge the 2 list in one by one manner\n",
    "    def mergeList(self, l1:ListNode, l2:ListNode):\n",
    "        while l1 and l2:\n",
    "            temp1, temp2 = l1.next, l2.next\n",
    "\n",
    "            l1.next = l2\n",
    "            l1 = temp1\n",
    "\n",
    "            l2.next = l1\n",
    "            l2 = temp2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        # 思路：1.先找到链表中点，断开 2.翻转第二个链表 3.两个链表节点一一合并\n",
    "        # step 1：找链表中点，断开。方法：设置快慢指针，直到快指针到达链表尾部，则慢指针的下一个节点为第二个链表的头节点\n",
    "        dummy = ListNode() # 设置一个哑节点，快慢指针从这里开始\n",
    "        dummy.next = head #千万不要漏掉这一步\n",
    "        slow, fast = dummy, dummy\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next #slow.next是后一个链表\n",
    "        second_head = slow.next\n",
    "        slow.next = None #稳妥起见，把链表断开\n",
    "        # step2: 翻转链表\n",
    "        second_head_new = self.reverse(second_head) \n",
    "        # step3：一一合并两链表的节点\n",
    "        self.link(head, second_head_new)\n",
    "    \n",
    "    def reverse(self, head_n: ListNode):\n",
    "        cur, pre = head_n, None\n",
    "        while cur:\n",
    "            next_n = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = next_n\n",
    "        return pre\n",
    "    \n",
    "    def link(self, first: ListNode, second: ListNode):\n",
    "        if not second:\n",
    "            return first # 注意这里，当second为None时：first可能还有一个或者也为None\n",
    "        tmp_1 = first.next\n",
    "        first.next = second\n",
    "        tmp_2 = second.next\n",
    "        second.next = self.link(tmp_1, tmp_2)\n",
    "        return first\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        if not head:\n",
    "            return head\n",
    "        slow = fast = head\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        bp = slow\n",
    "        p = slow.next\n",
    "        slow.next = None\n",
    "        while p:\n",
    "            tmp = p.next\n",
    "            p.next = slow\n",
    "            slow = p\n",
    "            p = tmp\n",
    "        self.merge(head,slow,bp)\n",
    "    \n",
    "    def merge(self,x,y,gap):\n",
    "        if x == gap:\n",
    "            x.next = None\n",
    "            return\n",
    "        if not y:\n",
    "            return\n",
    "        xn = x.next\n",
    "        yn = y.next\n",
    "        x.next = y\n",
    "        y.next = xn\n",
    "        self.merge(xn,yn,gap)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: Optional[ListNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        ## 1. 找到中点n: 双指针\n",
    "        ## 2. 从第n位置开始反转链表\n",
    "        ## 3. 合并两个链表\n",
    "\n",
    "        def findMiddle(head):\n",
    "            slow, fast = head, head\n",
    "            while fast.next and fast.next.next:\n",
    "                slow = slow.next\n",
    "                fast = fast.next.next\n",
    "            return slow\n",
    "        \n",
    "        def reverseList(head):\n",
    "            if not head or not head.next:\n",
    "                return head\n",
    "            resNode = reverseList(head.next)\n",
    "            head.next.next = head\n",
    "            head.next = None\n",
    "            return resNode\n",
    "\n",
    "        def mergeList(l1, l2):\n",
    "            # 这段代码不对，原因是什么？\n",
    "            # phead = p = ListNode(0)\n",
    "            # while l1 and l2:\n",
    "            #     p.next = l1\n",
    "            #     p = p.next\n",
    "            #     p.next = l2\n",
    "            #     p = p.next\n",
    "            #     l1 = l1.next  \n",
    "            #     l2 = l2.next\n",
    "            # p.next = l1 if l1 else l2\n",
    "            # return phead.next\n",
    "\n",
    "            while l1 and l2:\n",
    "                l1_tmp = l1.next\n",
    "                l2_tmp = l2.next\n",
    "                l1.next = l2\n",
    "                l1 = l1_tmp\n",
    "                l2.next = l1\n",
    "                l2 = l2_tmp\n",
    "\n",
    "        \n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        mid_node = findMiddle(head)\n",
    "        l1, l2 = head, mid_node.next\n",
    "        mid_node.next = None\n",
    "        l2 = reverseList(l2)\n",
    "        res = mergeList(l1, l2)\n",
    "        return res\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "\n",
    "class Solution:\n",
    "    def Reverse(self,head):\n",
    "        if head is None or head.next is None:\n",
    "            return head\n",
    "        p = self.Reverse(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return p\n",
    "    def findMid(self,head):\n",
    "        slow = fast = head\n",
    "        while fast is not None and fast.next is not None:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        return slow\n",
    "    def mergeList(self,headA,headB):\n",
    "        pointA = headA\n",
    "        pointB = headB\n",
    "        while pointA and pointB:\n",
    "            tmp_nodeA = pointA.next\n",
    "            tmp_nodeB = pointB.next\n",
    "            pointA.next = pointB\n",
    "            pointA = tmp_nodeA\n",
    "            pointB.next = pointA\n",
    "            pointB = tmp_nodeB\n",
    "    def reorderList(self, head: Optional[ListNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        if head is None:\n",
    "            return head\n",
    "        midhead = self.findMid(head)\n",
    "        l1 = head\n",
    "        l2 = self.Reverse(midhead.next)\n",
    "        # print(l2.next)\n",
    "        midhead.next = None\n",
    "        self.mergeList(l1,l2)\n",
    "        # return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: Optional[ListNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        if not head or not head.next:\n",
    "            return\n",
    "        \n",
    "        def reverse(node):\n",
    "            if not node or not node.next:\n",
    "                return node\n",
    "            ret = reverse(node.next)\n",
    "            node.next.next = node\n",
    "            node.next = None\n",
    "            return ret\n",
    "\n",
    "        slow, fast = head, head\n",
    "        while fast.next and fast.next.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        l1, l2 = head, slow.next\n",
    "        l2 = reverse(l2)\n",
    "        slow.next = None\n",
    "        while l1 and l2:\n",
    "            l1n, l2n = l1.next, l2.next\n",
    "            l1.next = l2\n",
    "            l1 = l1n\n",
    "            l2.next = l1\n",
    "            l2 = l2n\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: Optional[ListNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        def middleNode(head):\n",
    "            if not head or not head.next:\n",
    "                return head\n",
    "            slow,fast=head,head\n",
    "            while fast and fast.next:\n",
    "                fast = fast.next.next\n",
    "                slow = slow.next\n",
    "            return slow\n",
    "        \n",
    "        # reverse\n",
    "        def reverse(head):\n",
    "            p = head\n",
    "            if not p or not p.next:\n",
    "                return p\n",
    "            while p.next:\n",
    "                prev = p \n",
    "                p = p.next\n",
    "            prev.next = None \n",
    "            p.next = reverse(head)\n",
    "            return p\n",
    "        \n",
    "        mid = middleNode(head)\n",
    "        head2 = reverse(mid)\n",
    "\n",
    "        p1,p2 = head,head2\n",
    "        while p2.next:\n",
    "            np1 = p1.next\n",
    "            np2 = p2.next\n",
    "            p1.next = p2\n",
    "            p2.next = np1 \n",
    "            p1 = np1\n",
    "            p2 = np2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: Optional[ListNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        p1 = head\n",
    "        p2 = head\n",
    "        while p2.next and p2.next.next:\n",
    "            p1 = p1.next\n",
    "            p2 = p2.next.next\n",
    "        pre = None\n",
    "        cur = p1.next\n",
    "        p1.next = None\n",
    "        def reverse(h):\n",
    "            if not h or not h.next:\n",
    "                return h\n",
    "            result = reverse(h.next)\n",
    "            h.next.next = h\n",
    "            h.next = None\n",
    "            return result\n",
    "        pre = reverse(cur)\n",
    "        # while cur:\n",
    "        #     temp = cur.next\n",
    "        #     cur.next = pre\n",
    "        #     pre = cur\n",
    "        #     cur = temp\n",
    "        while pre:\n",
    "            temp1, temp2 = head.next, pre.next\n",
    "            head.next, pre.next = pre, temp1\n",
    "            head = temp1\n",
    "            pre = temp2\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
